package com.atwy.graph.undirectedgraph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 小王子火
 * @Date: 2022/3/8
 * BFS:广度搜索
 * 单点最短路径: 给定一幅图和一个起点s，从s到给定目的顶点v是否存在一条路径？
 * 如果有，找出最短的那条（所含边数最少）
 * 对于从 s 可达的任意顶点 v，广度优先搜索都能找到一条从 s 到 v 的最短路径（没有其他从 s 到 v 的路径所含的边比这条路径更少）
 */
public class BreadthFirstSearch {
    /**
     * 这个顶点上调用过dfs()了吗？
     */
    private boolean[] marked;
    private int count;
    /**
     * 从起点到一个顶点的已知路径上的最后一个顶点
     * 是一棵父链接表示的树
     * edgeTo[w]=v,表示 v 是 w 的前驱节点
     */
    private int[] edgeTo;
    /**
     * 起点
     */
    private int s;

    public BreadthFirstSearch(IGraph graph,int s) {
        marked = new boolean[graph.V()];
        edgeTo = new int[graph.V()];
        this.s = s;
        bfs(graph,s);
    }

    /**
     * 广度优先搜索
     * @param graph
     * @param s
     */
    private void bfs(IGraph graph, int s) {
        // 依次访问 起点s的相邻节点，
        marked[s] = true;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(s);
        while (!queue.isEmpty()){
            Integer v = queue.poll();
            for(int w : graph.adj(v)){
                if(!marked[w]){
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.offer(w);
                }
            }
        }
    }
    /**
     * 顶点v到 起点s是否存在路径
     *
     * @param v
     * @return
     */
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public int[] getEdgeTo() {
        return edgeTo;
    }

    /**
     * 打印顶点到 起点s的路径
     *
     * @param v
     */
    public void printPath(int v) {
        if (!hasPathTo(v)) {
            System.out.println(v + "到起点" + s + "不存在路径");
            return;
        }
        printEdgeTo(v);
    }

    /**
     * edgeTo[v]=w,  说明 w 是 v的前驱，即w->v
     * 通过递归，后续输出得到正向路径
     * @param v
     */
    private void printEdgeTo(int v) {
        if (v == s) {
            System.out.print(v);
            return;
        }
        printEdgeTo(edgeTo[v]);
        System.out.print("->" + v);
    }
}
